package com.jz;

import com.future.util.TreeNode;

/**
 * Description: JZ79 判断是不是平衡二叉树
 *
 * @author weiruibai.vendor
 * Date: 2022/9/5 10:35
 */
public class JZ79 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.left.left = new TreeNode(4);
        root.left.left.left.left = new TreeNode(5);
        System.out.println(IsBalanced_Solution(root));

    }

    public static boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) {
            return true;
        }
        return process(root).isBalance;
    }

    private static Info process(TreeNode head) {
        if (head == null) {
            return new Info(0, true);
        }
        Info left = process(head.left);
        if (!left.isBalance) {
            return new Info(left.height + 1, false);
        }
        Info right = process(head.right);
        if (!right.isBalance) {
            return new Info(right.height + 1, false);
        }
        boolean isBalance = true;
        if (Math.abs(left.height - right.height) > 1) {
            isBalance = false;
        }
        int height = Math.max(left.height, right.height) + 1;
        return new Info(height, isBalance);
    }


    private static class Info {
        public Integer height;

        public Boolean isBalance;

        public Info(Integer height, Boolean isBalance) {
            this.height = height;
            this.isBalance = isBalance;
        }


    }
}
